# -*- coding: UTF-8 -*-
'''
Created on Dec 6, 2009

@author: pntruongan
'''

from encodeDecode import dataStructure
import sys

class generateCodeError(Exception):
    pass
class readCodeError(Exception):
    pass

class code:
    def _treeTravel(self, root, path, enDict, deDict):
        if root.Left == None and root.Right == None:
            enDict.update({root.item[0] : path})
            deDict.update({path: root.item[0]})
        else:
            self._treeTravel(root.Left, path + '0', enDict, deDict)
            self._treeTravel(root.Right, path + '1', enDict, deDict)
            
    def _readFrequenceStatistic(self, freqStat):
        queue = dataStructure.priorityQueue()
        for i in freqStat.FrequenceDictionary.items():
            node = dataStructure.BTNode(i, None, None)
            queue.push(node)
        
        if queue.count() < 2 :
            raise generateCodeError()
        encodeDictionary = {}
        decodeDictionary = {}
        
        while (queue.count() > 1):
            a = queue.pop()
            b = queue.pop()
            
            newNode = dataStructure.BTNode((None, a.item[1] + b.item[1]), a, b)
            queue.push(newNode)
            
        root = queue.pop()
        
        #travel through the tree to get the code
        self._treeTravel(root, "",encodeDictionary, decodeDictionary)
        
        return encodeDictionary, decodeDictionary
        
    def _readEncodedFile(self, path):
        file = open(path, "r")
        try:
            encodeDict = {}
            decodeDict = {}
            a = file.readline().split()
            symbolLength = int(a[1])
            codePageLen = file.readline().split()[1]
            
            for i in range(codePageLen):
                if (symbolLength == 0):
                    ln = file.readline()
                    if ln != "":
                        ln = ln.split()
                        encodeDict.update({ln[0] : ln[1]})
                        decodeDict.update({ln[1] : ln[0]})
                    else:
                        #we are dealing with the "\n" symbol
                        ln = file.readline()
                        encodeDict.update({"\n" : ln})
                        decodeDict.update({ln: "\n"})
                else:
                    #The Non-UTF8 file.
                    symbol = file.read(symbolLength)
                    code = file.readline()
                    encodeDict.update({symbol : code})
                    decodeDict.update({code : symbol})
            return symbolLength, encodeDict, decodeDict
        except :
            raise readCodeError(), path

    def _calculateCodeLength(self):
        if not self.encodeDictionary and self.frequenceDictionary :
            codeLen = 0
            for i in self.frequenceDictionary.keys():
                codeLen += self.frequenceDictionary[i] * len( self.encodeDictionary[i])
            return codeLen
        
        return None

    def __init__(self, source):
        self.encodeDictionary = None # a dictionary with symbols and their code
        self.decodeDictionary = None # a dictionary with code and the symbol it represent
        self.frequenceDictionary = None
        self.codeLen = None
        if isinstance(source, FrequenceStatistics):
            #create the huffman tree
            self.symbolLength = source.symbolLength
            self.frequenceDictionary = source.FrequenceDictionary
            self.encodeDictionary, self.decodeDictionary = self._readFrequenceStatistic(source)
            self.codeLen = self._calculateCodeLength()
        else:
            self.symbolLength, self.encodeDictionary, self.decodeDictionary = self._readEncodedFile(source)
            
    def __str__(self):
        result = ""
        if (self.symbolLength == 0):
            result = u"SymbolLength " + str(self.symbolLength) + "\n"
            result += u"CodePageLength " + str(len(self.encodeDictionary.items())) + "\n"
            for i in self.encodeDictionary.items():
                result += i[0] + " " + str(i[1]) + "\n"
        else:
            result = "SymbolLength " + str(self.symbolLength) + "\n"
            result += "CodePageLength " + str(len(self.encodeDictionary.items())) + "\n"
            for i in self.encodeDictionary.items():
                result += i[0] + " " + str(i[1]) + "\n"
        return result
    
    def decode(self, encodedFilePath, outFilePath):
        pass
    
    def encode(self,sourceFilePath, outFilePath):
        source = open(sourceFilePath, "r")
        output = open(outFilePath, "w")
        
        output.write(self.__str__())
        #output.flush()
        bitwrt = dataStructure.bitWriter(output)
        while 1:
            if (self.symbolLength == 0):
                ln = unicode(source.readline(), errors='replace')
                
                if (ln == ""):
                    break
                
                for i in ln:
                    code = self.encodeDictionary[i]
                    bitwrt.write(code)
            else:
                str = source.read(self.symbolLength)
                if (str == ""):
                    break
                code = self.encodeDictionary[str]
                bitwrt.write(code)
        bitwrt.end(True)
        pass
    

class FrequenceStatistics:
    #symbol is a byte array with length can be specified in constructor
    def __init__(self, sourcePath, symbolLength = None):
        '''
        sourcePath: Path to source file
        symbolLength: The length in byte of a single symbol, must be smaller than the file itself.
        If source is UTF-8 or strictly ASCII symbolLength = 0 can be specified
        '''
        self.code = None
        self.__FrequenceDictionary = None #A hash table (dictionary)  with symbols their frequency (number of time they appear)
        self.symbolLength = symbolLength
        
        if symbolLength == None:
            self.__FrequenceDictionary = {}
            self.symbolLength = -1
            for i in sourcePath:
                if (self.__FrequenceDictionary.has_key(i)):
                    self.__FrequenceDictionary[i] += 1
                else:
                    self.__FrequenceDictionary.update({i:1})
            return 
        
        file = open(sourcePath, "r")
        self.__FrequenceDictionary = {}    
        try:
            if (symbolLength == 0):
                #we are reading a text file, and we also assume that it's UTF-8 encoding
                #File encoding don't affect the correctness of huffman anyway
                #But it may help increase the effectiveness
                while 1:
                    #read one line
                    ln = file.readline()
                    
                    if ln == "":
                        break
                    
                    #convert it to unicode utf-8
                    ln = unicode(ln, errors='replace')
                    
                    for k in ln:
                        if self.__FrequenceDictionary.has_key(k):
                            self.__FrequenceDictionary[k] += 1
                        else:
                            self.__FrequenceDictionary.update({k: 1})
            elif symbolLength > 0:
                #We are dealing with binary file
                while 1:
                    bytes = file.read(self.symbolLength)
                    if len(bytes) == 0:
                        break
                    
                    if (self.__FrequenceDictionary.has_key(bytes)):
                        self.__FrequenceDictionary[bytes] += 1
                    else:
                        self.__FrequenceDictionary.update({bytes : 1})
            file.close()
            
        except Exception, message:
            print >> sys.stderr,"An error occur while reading " + sourcePath , message 

        
    def _getFrequenceStatistic(self):
        return self.__FrequenceDictionary 
    FrequenceDictionary = property(_getFrequenceStatistic)
    
    
    def __str__(self):
        result = u'symbolLength ' + str( self.symbolLength) + "\n"
        if (self.symbolLength == 0):
            for i in self.__FrequenceDictionary.items():
                result += i[0] + " " + str(i[1]) + "\n"
        else:
            for i in self.__FrequenceDictionary.items():
                result += str(i[0]) + " " + str(i[1]) + "\n"

        return result 
    
    def generateCode(self):
        return code(self)
    